package leetcode.linkedlist;

import java.util.Stack;

import leetcode.linkedlist.model.ListNode;

public class LeetCode234 {
    public boolean isPalindrome(ListNode head) {
        boolean tryFind = false;
        int length = 0;
        ListNode h = head;
        while (h != null) {
            length++;
            h = h.next;
        }
        if (length < 2) {
            return true;
        }
        // 1 2 3 => 2 length/2 + 1
        // 1 2 3 4 => 2 length /2
        // 1 2
        Stack<ListNode> stack = new Stack<>();
        h = head;
        for (int i = 0; i < length; i++) {
            if (h == null) {
                break;
            }
            if (i < length / 2) {
                stack.push(h);
            } else if (i == length / 2 && length % 2 != 0) {
                // do nothing
            } else {
                tryFind = true;
                ListNode n = stack.pop();
                if (n.val != h.val) {
                    return false;
                }
            }
            h = h.next;
        }
        return tryFind;
    }
}
